package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.utils.ParseUtils;

import java.util.List;
import java.util.Random;

//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
// 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
// 示例 1:
//输入: [3,2,1,5,6,4], k = 2
//输出: 5
// 示例 2:
//输入: [3,2,3,1,2,4,5,5,6], k = 4
//输出: 4
// 提示：
// 1 <= k <= nums.length <= 105
// -104 <= nums[i] <= 104
// Related Topics 数组 分治 快速选择 排序 堆（优先队列）
// 👍 1947 👎 0


public class Solution215 {
	private final static Random random = new Random(System.currentTimeMillis());

	public int findKthLargest(int[] nums, int k) {
		int len = nums.length;
		int target = len - k;
		int left = 0;
		int right = len - 1;
		while (true) {
			int prvotIndex = partition(nums, left, right);
			if (prvotIndex == target) {
				return nums[prvotIndex];
			} else if (prvotIndex < target) {
				left = prvotIndex + 1;
			} else {
				right = prvotIndex - 1;
			}
		}
	}

	public int partition(int[] nums, int left, int right) {
		int randomIndex = left + random.nextInt(right - left + 1);//??
		swap(nums, left, randomIndex);
		int privot = nums[left];
		int le = left + 1;
		int ge = right;
		while (true) {
			while (le <= ge && nums[le] < privot) {
				le++;
			}
			while (le <= ge && nums[ge] > privot) {
				ge--;
			}
			if (le > ge) {
				break;
			}
			swap(nums, le, ge);
			le++;
			ge--;
		}
		swap(nums, le, ge);
		return ge;
	}

	private void swap(int[] nums, int index1, int index2) {
		int temp = nums[index1];
		nums[index1] = nums[index2];
		nums[index2] = temp;
	}

	public static void main(String[] args) {
		Solution215 solution = new Solution215();
		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
//		System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
//		System.out.println(solution.findKthLargest(new int[]{1, 3, 1, 3, 100}));
	}

}
